//统计一个数字在排序数组中出现的次数。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: 2 
//
// 示例 2: 
//
// 
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: 0 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// nums 是一个非递减数组 
// -10⁹ <= target <= 10⁹ 
// 
//
// 
//
// 注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-
//position-of-element-in-sorted-array/ 
// Related Topics 数组 二分查找 👍 325 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer53_1 {
    public int search(int[] nums, int target) {
        int numIndex = findNumIndex(nums, target, 0, nums.length-1);
        if(numIndex == -1) return 0;
        int count = 1;
        int statIndex = numIndex-1;
        while(statIndex >= 0 && nums[statIndex--] == target) {
            count++;
        }
        statIndex = numIndex+1;
        while(statIndex <= nums.length-1 && nums[statIndex++] == target) {
            count++;
        }
        return count;
    }

    //二分查找
    public int findNumIndex(int[] nums, int target, int left, int right){
        while(left <= right){ //一定要等于，否则{1}，1 就不对了
            int mid = left + (right - left) /2 ;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) return findNumIndex(nums,target,left,mid-1);
            else return findNumIndex(nums,target,mid+1,right);
        }
        return -1;
    }

    public static void main(String[] args) {
        new SolutionOffer53_1().search(new int[]{1},1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
